The existing cloud outsourcing privacy-preserving k-means clustering schemes have the problem of low efficiency and the problem of returning unreasonable clustering results when the cloud server is untrusted or attacked by hackers. Therefore, a cloud outsourcing verifiable privacy-preserving k-means clustering scheme that can be applied to multi-party privacy-preserving scenarios was proposed. Firstly, an improved clustering initialization method suitable for cloud outsourcing scenarios was proposed to effectively improve the iterative efficiency of the algorithm. Secondly, the multiplicative triple technology was used to design the safe Euclidean distance algorithm, and the garbled circuit technology was used to design the algorithm for safe calculation of the minimum value. Finally, a verification algorithm was proposed, making the users only need one round of communication to verify the clustering results. And after the data outsourcing, the algorithm training was performed on the cloud entirely, which was able to effectively reduce the interactions between users and the cloud. Simulation results show that the accuracy of the proposed scheme is 97% and 93% on the datasets Synthetic and S1 respectively, indicating that the privacy-preserving k-means clustering is similar to the plaintext k-means clustering, and is suitable for medical, social sciences and business fields.